// 抽象一个方法getNode用来获取某个索引下的节点，方便后续方法使用
// 在新增，删除的方法中要注意正确更新头节点，尾节点和链表数量，注意控制边界条件，如操作的索引正好是头节点或尾节点的时候

// 思路，注意链表操作中虚拟节点的使用

function ListNode(val = 0, next = null) {
    this.val = val
    this.next = next
}

function MyLinkedList() {
    this._size = 0
    this._head = null
    this._tail = null
}

MyLinkedList.prototype.getNode = function (index) {
    if (index < 0 || index >= this._size) {
        return null
    }
    let dummyHead = new ListNode(0, this._head)
    let cur = dummyHead
    while (index-- >= 0) {
        cur = cur.next
    }
    return cur
}

MyLinkedList.prototype.get = function (index) {
    let node = this.getNode(index)
    return node === null ? -1 : node.val
}

MyLinkedList.prototype.addAtHead = function (val) {
    let newHead = new ListNode(val, this._head)
    this._size++
    this._head = newHead
    // 也要考虑空节点的情况
    if (!this._tail) {
        this._tail = newHead
    }
}

MyLinkedList.prototype.addAtTail = function (val) {
    let newTail = new ListNode(val)
    // 如果本来就是空链表，那就把新的节点赋值给head和tail
    if (!this._tail) {
        this._tail = newTail
        this._head = newTail
    } else {
        // 否则添加到尾部
        this._tail.next = newTail
        this._tail = newTail
    }
    // 记得更新size
    this._size++
}

MyLinkedList.prototype.addAtIndex = function (index, val) {
    if (index > this._size) {
        return
    }
    // 添加到头部，添加到尾部
    if (index === this._size) {
        this.addAtTail(val)
    } else if (index <= 0) {
        this.addAtHead(val)
    } else {
        // 找到目标位置的前一位node
        let node = this.getNode(index - 1)
        node.next = new ListNode(val, node.next)
        this._size++
    }
}

MyLinkedList.prototype.deleteAtIndex = function (index) {
    if (index < 0 || index >= this._size) {
        return
    }
    // 删除的时候也需要考虑到删除头结点和尾节点
    // 如果删除的是头节点，并且只有一个节点，应该更新tail
    if (index === 0) {
        this._head = this._head.next
        if (this._size === 1) {
            this._tail = null
        }
    } else {
        let node = this.getNode(index - 1)
        node.next = node.next.next
        // 如果删除掉尾节点，要更新新的tail
        if (this._size - 1 === index) {
            this._tail = node
        }
    }
    this._size--
}
